// 稳定的排序算法 冒泡， 插入， 归并， 计数
// 冒泡和插入排序的时间复杂的度都为O(n)2
function bubbleSort(arr = []) {
    let len = arr.length;
    for(let  i = 0; i < len; i++) {
        for (let j = 0; j < len - i; j++) {
            if(arr[j+1] < arr[j]) {
                let temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}
const arr1 = [4,1,5,0];
/* 
 形参是按照值进行传递的
  - 如果插入的实参是基本数据类型,形参指向的就是这个值而不是基本数据类型对应的空间地址
  - 如果参数是引用数据类型的， 形参和实参指向的是这个引用类型的空间地址。除非形参又指向一个新的空间否则就对实参进行了更改
 */
//   bubbleSort(arr1); 
//   console.log(arr1)

/**
 * 
 *插入排序： 稳定
思路： 每次拿当前循环的下一项（base）和前面的每一项比较，满足条件，就进行进行下一轮的
 */

  function insertSort(arr = []) {
      let len = arr.length;
      let i = 0;
      while(i < len) { // 外层 找出当前base
          let base = arr[i+1];
          let baseIndex = i+1;
          while(baseIndex > 0) { //内层 base从后向前依次比较
              if( arr[baseIndex-1] > base) {
                  let temp = arr[baseIndex-1];
                  arr[baseIndex-1] = base;
                  arr[baseIndex] = temp;
              }
              baseIndex --;
          }
          i++;
      }
  }
//   insertSort(arr1); 
//  console.log(arr1)

 /**
  * 插入排序的优化算法： 希尔排序
  * 说白了就是优化每一次扎入的步伐次初用gap
  */
function shellSort(arr) {
    let n = arr.length, gap = 1, current, prevIndex;
    while(gap < n/3) {
        gap = gap*3+1;
    }
    for (gap; gap > 0 ; gap =  Math.floor(gap/3)) {
        for(let i = gap; i < n; i++) {
            prevIndex = i - gap;
            current = arr[i];
            while((prevIndex >= 0)&&(arr[prevIndex] < current)) {
                arr[prevIndex + gap] = arr[prevIndex];
                prevIndex -= gap;
            }
            arr[prevIndex] = current;
        }
    }
}

 // 归并排序
 /*
 * 归并操作，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
    如　设有数列[4,1,5,0]
    初始状态：6,202,100,301,38,8,1
    第一次归并后：左边[1][4] -> [1,4]  右边 [5],[0] -->[0,5] 比较次数：2；
    第二次归并后：[0,1,4,5] 比较次数：2；
    总的比较次数为 4 数组多的话一样，就是多走几次递归。
 */
    function　merge(left, right){
        var　result=[];
        while(left.length>0 && right.length>0){
            if(left[0]<right[0]){
                result.push(left.shift());
            }else{
                result.push(right.shift());
            }
        }
        return　result.concat(left).concat(right); // 排序后的数据 左右分半后排序后，组成left和right。然后left和right再次比较放到新的数组中
    }
    function　mergeSort(items){
        if(items.length == 1){
            return　items;
        }
        var　middle = Math.floor(items.length/2),
        left = items.slice(0, middle),
        right = items.slice(middle);
        // js引擎解析的是子上而下，从做左到右解析。
        //因此会把分半后的左边的排完序后再排右边的
        return　merge(mergeSort(left), mergeSort(right)); 
    }
    // const arr = mergeSort(arr1)
    // console.log(arr);

    // 计数排序

// 1.10 基数排序
// 分类 算法
// 基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
//由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
// 1. 基数排序 vs 计数排序 vs 桶排序
// 基数排序有两种方法：
// 这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
// 基数排序：根据键值的每位数字来分配桶；
// 计数排序：每个桶只存储单一键值；
// 桶排序：每个桶存储一定范围的数值；
// 2. LSD 基数排序动图演示
/**
 * arr：排序的数组
 * maxDigit: 最大数据的位数
 * %取模运算代表 商为整数时的余数
 */

function radixSort(arr, maxDigit) {
    const counter = [];
    let mod = 10;
    let dev = 1;
    for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {//根据位数来对数组中数据进行分组
        // 按照个位分组装到桶里， 第二轮 按照十位 第三轮按照百位
        for(let j = 0; j < arr.length; j++) {
            let bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        // 把数据分组里取出来 
        for(let x = 0; x < counter.length; x++) {
           const bucket = counter[x];
           while(Array.isArray(bucket)) {
            arr.push(bucket.shift())
           }
        }
    }
}
const arr2 = [0,50, 2, 31, 4, 48]
radixSort(arr2,2)
console.log(arr2)